﻿/**
 * Copyright (C) 2011 original author and authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NGuice.Inject.Internal.Util
{
    /// <summary>
    /// 一个高性能的，不可变的列表实现
    /// </summary>
    /// <typeparam name="E"></typeparam>
    public abstract class ImmutableList<E> : ImmutableCollection<E>, IList<E>
    {
        internal static readonly ImmutableList<E> EMPTY_IMMUTABLE_LIST = new EmptyImmutableList();

        // Casting to any type is safe because the list will never hold any elements.
        public static ImmutableList<E> Of()
        {
            return (ImmutableList<E>)EMPTY_IMMUTABLE_LIST;
        }

        /// <summary>
        /// 返回包含一个单独元素的不可变有序列表，如果元素为null，将抛出NullReference异常
        /// </summary>
        /// <param name="element"></param>
        /// <returns></returns>
        public static ImmutableList<E> Of(E element)
        {
            // TODO: evaluate a specialized SingletonImmutableList
            return new RegularImmutableList(CopyIntoArray(element));
        }

        /// <summary>
        /// 返回包含给定元素的不可变有序列表
        /// </summary>
        /// <param name="e1"></param>
        /// <param name="e2"></param>
        /// <returns></returns>
        public static ImmutableList<E> Of(E e1, E e2)
        {
            return new RegularImmutableList(CopyIntoArray(e1, e2));
        }

        /// <summary>
        /// 返回包含给定元素的不可变有序列表
        /// </summary>
        /// <param name="e1"></param>
        /// <param name="e2"></param>
        /// <param name="e3"></param>
        /// <returns></returns>
        public static ImmutableList<E> Of(E e1, E e2, E e3)
        {
            return new RegularImmutableList(CopyIntoArray(e1, e2, e3));
        }

        /// <summary>
        /// 返回包含给定元素的不可变有序列表
        /// </summary>
        /// <param name="e1"></param>
        /// <param name="e2"></param>
        /// <param name="e3"></param>
        /// <param name="e4"></param>
        /// <returns></returns>
        public static ImmutableList<E> Of(E e1, E e2, E e3, E e4)
        {
            return new RegularImmutableList(CopyIntoArray(e1, e2, e3, e4));
        }

        /// <summary>
        /// 返回包含给定元素的不可变有序列表
        /// </summary>
        /// <param name="e1"></param>
        /// <param name="e2"></param>
        /// <param name="e3"></param>
        /// <param name="e4"></param>
        /// <param name="e5"></param>
        /// <returns></returns>
        public static ImmutableList<E> Of(E e1, E e2, E e3, E e4, E e5)
        {
            return new RegularImmutableList(CopyIntoArray(e1, e2, e3, e4, e5));
        }

        /// <summary>
        /// 返回包含给定元素的不可变有序列表
        /// </summary>
        /// <param name="elements"></param>
        /// <returns></returns>
        public static ImmutableList<E> Of(params E[] elements)
        {
            return (elements.Length == 0) ? ImmutableList<E>.Of() : new RegularImmutableList(CopyIntoArray(elements));
        }

        /// <summary>
        /// </summary>
        /// <param name="extends"></param>
        /// <returns></returns>
        public static ImmutableList<E> CopyOf<X>(IEnumerable<X> elements) where X : E
        {
            if (elements is ICollection<X>)
            {
                ICollection<X> coll = (ICollection<X>)elements;
                return CopyOfInternal<X>(coll);
            }
            else
            {
                return CopyOfInternal<X>(Lists.NewArrayList(elements));
            }
        }

        public static ImmutableList<E> CopyOf<X>(IEnumerator<X> elements) where X : E
        {
            return CopyOfInternal<X>(Lists.NewArrayList(elements));
        }

        private static ImmutableList<E> CopyOfInternal<X>(List<X> list) where X : E
        {
            return (list.Count == 0) ? ImmutableList<E>.Of() : (ImmutableList<E>)new RegularImmutableList(NullChecked(list.Cast<object>().ToArray()));
        }

        private static ImmutableList<E> CopyOfInternal<X>(ICollection<X> collection) where X : E
        {
            int size = collection.Count;
            return (size == 0) ? ImmutableList<E>.Of() : ImmutableList<E>.CreateFromIterable(collection, size);
        }

        /// <summary>
        /// 检查所有元素不能为null
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        /// <exception cref="NullReferenceException">如果有元素为null</exception>
        private static object[] NullChecked(object[] array)
        {
            for (int i = 0, len = array.Length; i < len; i++)
            {
                if (array[i] == null)
                {
                    throw new NullReferenceException("at index " + i);
                }
            }
            return array;
        }

        private ImmutableList() { }

        public abstract int IndexOf(E item);

        public virtual void Insert(int index, E item)
        {
            throw new NotSupportedException();
        }

        public virtual void RemoveAt(int index)
        {
            throw new NotSupportedException();
        }

        public abstract E this[int index]
        {
            get;
            set;
        }


        //public abstract int Count
        //{
        //    get;
        //}

        //public abstract IEnumerator<E> GetEnumerator();

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private sealed class EmptyImmutableList : ImmutableList<E>
        {
            private static readonly EmptyEnumerator<E> EMPTY_ENUMERATOR = new EmptyEnumerator<E>();

            public override int Count
            {
                get { return 0; }
            }

            public override IEnumerator<E> GetEnumerator()
            {
                return EMPTY_ENUMERATOR;
            }

            public override bool IsEmpty
            {
                get
                {
                    return true;
                }
            }

            public override bool Contains(E target)
            {
                return false;
            }

            private static readonly E[] EMPTY_ARRAY = new E[0];

            public override E[] ToArray()
            {
                return EMPTY_ARRAY;
            }

            public override int IndexOf(E item)
            {
                return -1;
            }

            public override E this[int index]
            {
                set
                {
                    throw new NotSupportedException();
                }
                get
                {
                    Preconditions.CheckElementIndex(index, 0);
                    throw new IndexOutOfRangeException();
                }
            }

            public override bool Equals(object o)
            {
                if (o is List<E>)
                {
                    List<E> that = (List<E>)o;
                    return that.Count == 0;
                }
                return false;
            }

            public override int GetHashCode()
            {
                return 1;
            }

            public override string ToString()
            {
                return "[]";
            }
        }

        private sealed class RegularImmutableList: ImmutableList<E>
        {
            private readonly int offset;
            private readonly int size;
            private readonly object[] array;

            public RegularImmutableList(object[] array, int offset, int size)
            {
                this.offset = offset;
                this.size = size;
                this.array = array;
            }

            public RegularImmutableList(object[] array)
                : this(array, 0, array.Length)
            {
            }

            public override bool IsEmpty
            {
                get
                {
                    return false;
                }
            }

            public override bool Contains(E target)
            {
                return IndexOf(target) != -1;
            }

            public override int IndexOf(E item)
            {
                if (item != null)
                {
                    for (int i = offset; i < offset + size; i++)
                    {
                        if (array[i].Equals(item))
                        {
                            return i - offset;
                        }
                    }
                }
                return -1;
            }

            public override int Count
            {
                get { return size; }
            }

            public override E[] ToArray()
            {
                E[] newArray = new E[Count];
                System.Array.Copy(array, offset, newArray, 0, size);
                return newArray;
            }

            public override E this[int index]
            {
                get
                {
                    Preconditions.CheckElementIndex(index, size);
                    return (E)array[index + offset];
                }
                set
                {
                    throw new NotSupportedException();
                }
            }

            public override IEnumerator<E> GetEnumerator()
            {
                Preconditions.CheckPositionIndex(0, size);
                return new InternalEnumerator(this);
            }

            private class InternalEnumerator : IEnumerator<E>
            {
                private RegularImmutableList list;

                private int index = -1;

                public InternalEnumerator(RegularImmutableList list)
                {
                    this.list = list;
                }

                public E Current
                {
                    get
                    {
                        E result;
                        try
                        {
                            result = list[index];
                        }
                        catch (IndexOutOfRangeException rethrown)
                        {
                            throw new NoSuchElementException();
                        }
                        return result;
                    }
                }

                public void Dispose()
                {
                    Reset();
                }

                object System.Collections.IEnumerator.Current
                {
                    get { return Current; }
                }

                private bool HasNext()
                {
                    return index < list.size;
                }

                public bool MoveNext()
                {
                    index++;
                    if (HasNext())
                    {
                        return true;
                    }
                    else
                    {
                        return false;
                    }
                }

                public void Reset()
                {
                    index = 0;
                }
            }

            public override bool Equals(object o)
            {
                if (o == this)
                {
                    return true;
                }
                if (!(o is List<E>))
                {
                    return false;
                }

                List<E> that = (List<E>)o;
                if (this.Count != that.Count)
                {
                    return false;
                }

                int index = offset;
                if (o is RegularImmutableList)
                {
                    RegularImmutableList other = (RegularImmutableList)o;
                    for (int i = other.offset; i < other.offset + other.size; i++)
                    {
                        if (!array[index++].Equals(other.array[i]))
                        {
                            return false;
                        }
                    }
                }
                else
                {
                    foreach (object element in that)
                    {
                        if (!array[index++].Equals(element))
                        {
                            return false;
                        }
                    }
                }
                return true;
            }

            public override int GetHashCode()
            {
                // not caching hash code since it could change if the elements are mutable
                // in a way that modifies their hash codes
                int hashCode = 1;
                for (int i = offset; i < offset + size; i++)
                {
                    hashCode = 31 * hashCode + array[i].GetHashCode();
                }
                return hashCode;
            }

            public string ToString()
            {
                StringBuilder sb = new StringBuilder(Count * 16);
                sb.Append('[').Append(array[offset]);
                for (int i = offset + 1; i < offset + size; i++)
                {
                    sb.Append(", ").Append(array[i]);
                }
                return sb.Append(']').ToString();
            }
        }

        private static object[] CopyIntoArray(params object[] source)
        {
            object[] array = new object[source.Length];
            int index = 0;
            foreach (object element in source)
            {
                if (element == null)
                {
                    throw new NullReferenceException("at index " + index);
                }
                array[index++] = element;
            }
            return array;
        }

        private static ImmutableList<E> CreateFromIterable<X>(IEnumerable<X> source, int estimatedSize)
            where X: E
        {
            object[] array = new object[estimatedSize];
            int index = 0;

            foreach (object element in source)
            {
                if (index == estimatedSize)
                {
                    // At least one element was added after our call to size().
                    estimatedSize = ((estimatedSize / 2) + 1) * 3;
                    array = CopyOf(array, estimatedSize);
                }
                if (element == null)
                {
                    throw new NullReferenceException("at index " + index);
                }
                array[index++] = element;
            }

            if (index == 0)
            {
                return Of();
            }

            if (index != estimatedSize)
            {
                array = CopyOf(array, index);
            }

            return new RegularImmutableList(array, 0, index);
        }

        // Avoid using Arrays.copyOf(), which is not present until JDK6.
        private static object[] CopyOf(object[] oldArray, int newSize)
        {
            object[] newArray = new object[newSize];
            System.Array.Copy(oldArray, 0, newArray, 0, Math.Min(oldArray.Length, newSize));
            return newArray;
        }

        /// <summary>
        /// 返回一个新的builder。生成的builder通过Builder构造器
        /// </summary>
        /// <typeparam name="E"></typeparam>
        /// <returns></returns>
        public static ImmutableListBuilder<E> Builder<E>()
        {
            return new ImmutableListBuilder<E>();
        }
    }

    /// <summary>
    /// 用于创建不可变的列表实例，特别是静态只读的列表（"constant lists"）
    /// <code>
    /// public static final ImmutableList<Color> GOOGLE_COLORS = new ImmutableList.Builder<Color>()
    ///       .AddAll(WEBSAFE_COLORS)
    ///       .Add(new Color(0, 191, 255))
    ///       .Build();
    /// }
    /// </code>
    /// Builder实例能够被重复使用--能够安全的调用Build多次来构建一系列的列表。每一个新的列表都包含之前创建的元素
    /// </summary>
    /// <typeparam name="E"></typeparam>
    public class ImmutableListBuilder<E>
    {
        private readonly List<E> contents = Lists.NewArrayList<E>();

        public ImmutableListBuilder() { }

        public ImmutableListBuilder<E> Add(E element)
        {
            Preconditions.CheckNotNull(element, "element cannot be null");
            contents.Add(element);
            return this;
        }

        public ImmutableListBuilder<E> AddAll<X>(IEnumerable<X> elements) where X : E
        {
            if (elements is ICollection<X>)
            {
                ICollection<X> collection = (ICollection<X>)elements;
                contents.Capacity = contents.Count + collection.Count;
            }
            foreach (X elem in elements)
            {
                Preconditions.CheckNotNull(elem, "elements contains a null");
                contents.Add(elem);
            }
            return this;
        }

        public ImmutableList<E> Build()
        {
            return ImmutableList<E>.CopyOf<E>(contents);
        }
    }
}
